def InsterSort(arr):
    for i in range (1,len(arr)):
        j = i-1
        if arr[j] > arr[i]:
            a = arr[j]
            arr[i] = arr[j]

        j = j-1
        while j >=0 and arr[j]>a:
            arr[j+1] =j
            j = j-1
        arr[j+1] = a

    return arr


if __name__ == '__main__':

    print(InsterSort([4,8,6,7,3,4,8,9]))